Berkhidmat sebagai Naib Presiden

Sebagai naib presiden, Megawati mempunyai kuasa yang besar kerana beliau menguasai banyak kerusi di DPR. Wahid mewakilkan kepadanya masalah di Ambon, walaupun beliau tidak berjaya.[13] Sewaktu Sesi Tahunan MPR yang diwujudkan pada Ogos 2000, ramai yang menganggap Wahid tidak menunaikan tanggungjawab sebagai presiden atau sebagai pentadbir. Wahid bertindak balas dengan ini dengan mengeluarkan satu keputusan presiden, yang memberikan kuasa harian Megawati kepada kerajaan.[13]

Kongres Nasional PDI-P 2000

Kongres PDI-P Pertama diadakan di Semarang, Jawa Tengah pada April 2000, di mana Megawati dipilih kembali sebagai Ketua untuk penggal ke-2.

Megawati menggabungkan kedudukannya dalam PDI-P dengan mengambil langkah-langkah yang keras untuk menghilangkan pesaing yang berpotensi.[14] Semasa pilihan raya untuk Pengerusi, dua calon lain muncul; Eros Djarot dan Dimyati Hartono. Mereka bertanding kerana mereka tidak mahu Megawati berkhidmat serentak sebagai kedua-dua kerusi dan naib presiden. Pencalonan Eros dari cawangan Jakarta Selatan dibatalkan oleh masalah keahlian. Eros tidak dibenarkan menyertai Kongres. Kecewa dengan apa yang dilihatnya sebagai kultus keperibadian yang berkembang di sekitar Megawati, Eros meninggalkan PDI-P. Pada Julai 2002, beliau membentuk Parti Kebangsaan Kebebasan Bebas. Walaupun pencalonan Dimyati tidak bertentangan dengan keras seperti Eros, beliau dipecat sebagai Ketua Cawangan Tengah PDI-P. beliau memegang jawatannya sebagai anggota Majlis Perwakilan Rakyat (DPR), tetapi bersara pada Februari 2002. Pada bulan April 2002, Dimyati membentuk Partai Pribumi Indonesia (PITA).

Perhubungan dengan Wahid dan kebangkitan jawatan presiden

Megawati mempunyai hubungan kedamaian dengan Wahid. Semasa rombakan Kabinet pada Ogos 2000, misalnya, Megawati tidak hadir untuk pengumuman barisan baru[15] Pada masa yang lain, apabila arus politik mula menentang Wahid, Megawati mempertahankannya dan membantah terhadap pengkritik.[16] Pada tahun 2001, Megawati mula menjauhkan dirinya dari Wahid sebagai Sidang Khas MPR yang mendekati dan prospeknya menjadi presiden yang bertambah baik. Walaupun beliau enggan membuat sebarang ulasan tertentu, beliau menunjukkan tanda-tanda mempersiapkan dirinya, mengadakan pertemuan dengan pemimpin parti sehari sebelum Sesi Khas bermula.